//
// Created by Administrator on 2023/8/8.
//
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int> &A, vector<int> &B) {
        set<int> setA;
        set<int> setB;
        vector<int> result(A.size(), 0);
        set<int> C;
        for (int i = 0; i < A.size(); ++i) {
            setA.insert(A[i]);
            setB.insert(B[i]);
            // 求 setA 和 setB 的交集
            set_intersection(setA.begin(), setA.end(), setB.begin(), setB.end(), inserter(C, C.begin()));
            result[i] = C.size();
        }
        return result;
    }
};

class Solution2 {
public:
    vector<int> findThePrefixCommonArray(vector<int> &a, vector<int> &b) {
        int n = a.size();
        vector<int> ans(n);
        long long p = 0, q = 0;
        // 位运算加速
        for (int i = 0; i < n; ++i) {
            p |= 1LL << a[i];
            q |= 1LL << b[i];
            // 计算一个 64 位无符号整数的二进制表示中 1 的个数
            ans[i] = __builtin_popcountll(p & q);
        }
        return ans;
    }
};

int main() {
    vector<int> A = {1, 3, 2, 4};
    vector<int> B = {3, 1, 2, 4};
    Solution2 solution;
    vector<int> result = solution.findThePrefixCommonArray(A, B);
    for (auto &x: result) cout << x << " ";
    cout << endl;
    return 0;
}